package com.fenqing.leetcode.code.t500_600;

import com.fenqing.annotations.Execute;
import com.fenqing.bean.TreeNode;
import com.fenqing.core.Topic;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author fenqing
 */
public class Topic652 extends Topic {
    /**
     * 构造器
     * @param input 输入
     */
    public Topic652(String input) {
        super(input);
    }

    @Execute
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> result = new ArrayList<>();
        findDuplicateSubtrees(root, new HashMap<>(), result);
        return result;
    }

    public String findDuplicateSubtrees(TreeNode root, Map<String, Boolean> hash, List<TreeNode> result) {
        if (root == null) {
            return "";
        }
        int val = root.val;
        String left = findDuplicateSubtrees(root.left, hash, result);
        String right = findDuplicateSubtrees(root.right, hash, result);
        String key = val + ":" + left  + ":" + right;
        Boolean aBoolean = hash.get(key);
        if (aBoolean != null && !aBoolean) {
            result.add(root);
            hash.put(key, true);
        } else {
            if (aBoolean == null) {
                hash.put(key, false);
            }
        }
        return key;
    }

    public static void main(String[] args) {
        Topic652 topic652 = new Topic652("""
                [1,2,3,4,null,2,4,null,null,4]
                """);
        List<TreeNode> run = topic652.run();
        System.out.println(run);
    }

}
